The problem of aliasing is well known in computer graphics. When scan converting a geometric primitive to a graphical display composed of pixels the simplest technique is to quantise the edges of the primitive to the nearest display pixels. This technique, whilst simple to implement and computationally efficient, generally provides a low quality image. This is because this technique results in quantisation noise appearing over distances of up to one pixel from the boundary of the geometric primitive and with intensity as great as 100% of the intensity of the rendered primitive (with respect to the background color).
In order to provide better image quality it is necessary to overcome these aliasing effects with antialiasing. Antialiasing is typically achieved by quantising edges with precision significantly higher than the width of one pixel, and using this sub-pixel position information to modulate the intensity with which boundary pixels are rendered. The distance over which the resultant quantisation noise is distributed remains unchanged at the width of one pixel, but the intensity is now modulated such that it decreases from a maximal value at distance zero, down to zero intensity at a distance of one pixel. The resulting image is generally much more pleasing to the eye, particularly when the pixels are close in size to the resolution limit of the eye.
A wide variety of approaches to perform antialiasing have been developed. Some approaches use geometric calculations on boundary pixels to determine the fractional area covered by the relevant graphical primitive, with the area fraction used to modulate the intensity of boundary pixels. This class of approach provides high accuracy for the modulation value, but is generally prohibitively expensive computationally. It also suffers from reduced quality when dealing with pixels that are crossed by the boundaries of multiple graphical primitives, as no account is taken of the degree of correlation between the edges of these separate graphical primitives.
Another class of antialiasing algorithms are the class of “super-sampling” antialiasing algorithms. These algorithms work by subdividing pixels into an array of sub-pixels. These sub-pixels are processed with the simple quantisation techniques used by systems that do not perform antialiasing, but the colors of the resultant sub-pixels are averaged to provide the antialiased color of the pixel itself. The array of sub-pixels is typically two dimensional, with the degree of antialiasing classified by the size of the array in X and Y dimensions—typical systems use “2×2” or “4×4” super-sampling. Brute force super-sampling is computationally expensive, whilst providing modest precision for the modulation value. Super-sampling also has the advantage of accurately handling pixels that are crossed by the boundaries of multiple geometric primitives.
The article “The A-buffer, An Antialiased Hidden Surface Method”, Loren Carpenter, Computer Graphics Vol. 18, No. 3, July 1984, introduced an antialiasing technique that has since been widely reused and modified. A central component of Carpenter's approach was to use a 4×8-bit mask to represent the sub-pixels covered by a geometric primitive. Processing of each pixel is similar to that used in systems that do not perform antialiasing, but a weighting derived from the proportion of affected sub-pixels expressed by the bit mask is incorporated to provide anti-aliasing. Intersecting edges are handled by performing set operations on their associated bit masks to account for the degree of correlation between the intersecting edges. This technique allows super-sampling to be performed without the high computational cost of the brute force technique of super-sampling.
Whilst substantially improving on the prior art, Carpenter's technique still leaves room for improvement. The memory requirements of Carpenter's technique are quite high, being at least 64 bits per pixel but ranging up to 192 bits for each geometric primitive/pixel boundary. For a large image with a large number of geometric primitives the memory requirements can be prohibitive, and are also difficult to accurately and reliably characterise prior to rendering. The need to calculate sub-pixel coverage for each geometric primitive/pixel boundary also adds to the computational expense of rendering.
A technique that provides the benefits of Carpenter's technique whilst reducing its memory requirements and computational expense would be highly advantageous for systems requiring fast, high quality rendering.